package sort;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Code03_HeapSort {

    //实现堆排序
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    //向堆中插入一个指定下标的元素
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {   //当要插入的数大于其父节点的时候  进行交换 并将现父节点设置为新的index
            swap(arr, index, (index - 1) /2);
            index = (index - 1)/2 ;
        }
    }

    /*
     * 某个数在index位置，看看能否往下沉
     * 不断和左右两个孩子比较
     * 较大的孩子如果大于当前的父   父节点下沉  较大的孩子上
     * index为当前节点下标  size为当前堆的大小
     * */
    public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {  //下方还有孩子的时候
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;  //left + 1 < size表示右孩子不越界
            largest = arr[largest] > arr[index] ? largest : index; //父亲和较大孩子之间谁大 把下标给largest
            if (largest == index) {  //停止下沉
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {

        //系统提供的优先队列 默认大根堆
        PriorityQueue<Integer> heap=new PriorityQueue<>();
        heap.add(1);
        heap.toString();



        int[] arr ={-3,-66,44,62,32,1,-44,1,17,31,8};
        printArray(arr);
        heapSort(arr);
        printArray(arr);
    }

}
